import entity.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class FindModeInBST {
    /*
    * 501. 二叉搜索树中的众数
    * 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
    * 如果树中有不止一个众数，可以按 任意顺序 返回。
    *
    * 假定 BST 满足如下定义：
    * 结点左子树中所含节点的值 小于等于 当前节点的值
    * 结点右子树中所含节点的值 大于等于 当前节点的值
    * 左子树和右子树都是二叉搜索树
    *
    * 中节点的数目在范围 [1, 10^4] 内
    * -10^5 <= Node.val <= 10^5
    *
    * 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
    * */
    public static void main(String[] args){

    }

    // 我的想法：中序遍历
    public int[] mySolution(TreeNode root){
        traversal(root);
        int[] result = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }
    int max = 1;
    int times = 1;
    TreeNode pre;
    List<Integer> res = new LinkedList<>();
    private void traversal(TreeNode root){
        if(root == null)
            return;
        traversal(root.left);
        if(pre != null){
            if(pre.val == root.val){
                times++;
                if(times > max){
                    res.clear();
                    res.add(root.val);
                    max = times;
                }
                else if (times == max){
                    res.add(root.val);
                }
            }
            else {
                times = 1;
                if (times == max)
                    res.add(root.val);
            }
        }
        else {
            res.add(root.val);
        }
        pre = root;
        traversal(root.right);
    }

    // 下面的逻辑更简洁清楚
    private void clearTraversal(TreeNode root){
        if(root == null)
            return;
        traversal(root.left);
        // 计数
        if(pre == null || pre.val != root.val)
            times = 1;
        else
            times++;
        // 更新结果
        if(times > max){
            res.clear();
            res.add(root.val);
            max = times;
        }
        else if (times == max)
            res.add(root.val);

        pre = root;
        traversal(root.right);
    }
}
